#include "stdlib.h"
#include "iostream"
int cmp(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}
/*****initial_fib[]******/
int fib[30] = {0};
void fib_array()
{
    fib[0] = 0;
    fib[1] = 1;
    int i = 2;
    while (i < 30)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
        i++;
    }
}
/*****initial_fib[]*****/
/*
fib[]=0,1,1,2,3,5,8,13,21,34...
*/
/******fib_search*******/
int fib_search(int a[], int n, int key)
{
    int k = 1;
    while (n + 1 > fib[k])
        k++;
    //mid与二分搜索不同
    int mid = n - fib[k - 2] + 1; //20-8+1--->13
    int f1 = fib[k - 2];
    int f2 = fib[k - 3];
    bool found = false;
    while (mid >= 0 && !found)
    {
        if (a[mid] == key)
        {
            break;
        }
        else if (a[mid] < key)
        {
            //右半区搜索 mid+f2;
            if (f1 == 1) //没找到！
                mid = -1;
            else
            {
                mid += f2;
                f1 = f1 - f2;
                f2 = f2 - f1;
            }
        }
        else if (a[mid] > key)
        {
            //左半区搜索 mid-f2;
            if (f2 == 0) //没找到！
                mid = -1;
            else
            {
                mid -= f2;
                int t = f1 - f2;
                f1 = f2;
                f2 = t;
            }
        }
    }
    if (found)
        return mid;
    else
        return -1;
}
void main()
{

    int a[20] = {5, 1, 3, 2, 6, 4, 9, 8, 7, 0,
                 11, 12, 15, 64, 33, 29, 15, 32, 27, 18};
    qsort(a, 20, sizeof(a[0]), cmp);
    fib_array();
    fib_search(a, 20, 64);
}